// @algorithm @lc id=802 lang=cpp 
// @title k-th-smallest-prime-fraction


// @test([1,2,3,5],3)=[2,5]
// @test([1,7],1)=[1,7]
using pii = pair<int,int>;
class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        int n = arr.size();
        auto cmp = [&](const pii&x, const pii&y){
            return arr[x.first] * arr[y.second] >  arr[y.first] * arr[x.second];
        };
        priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp);
        for(int i=1; i<n; i++) pq.push({0,i});
        for(int _=0; _<k-1; _++){
            auto [i,j] = pq.top(); pq.pop();
            if(i+1<j) pq.push({i+1, j});
        }
        auto [i,j] = pq.top();
        return {arr[i], arr[j]};
    }
};